Counting sort

Counting sort je algoritmus řazení, který je vhodný pro řazení velkého pole prvků, nabývajících jen malý počet různých diskrétních hodnot. Algoritmus řadí stabilně.

Předpoklady

Abychom mohli využít toto řazení, je třeba aby:

• Počet různých hodnot prvků (M) byl významně menší než celkový počet prvků (N). Rozsah hodnot (K) je lineární k N a hodnotami lze indexovat pole.
• Potřebujeme pomocné pole, ve kterém bychom mohli zapisovat a číst hodnotu četnosti v konstantním čase O(1). Tuto podmínku splňuje pole indexované hodnotou nebo hashem hodnoty prvku.
• Výstupní pole potřebujeme indexovat v konstantním čase.

Za těchto ,nebo i jiných, předpokladů dostaneme algoritmus, který je lineární k počtu prvků N, což je cílem.

Hašování se meze nekladou, ale třídění, v odborných kruzích nazýváno řádění, obvykle nedopadne dobře, ale dopadne náhodně.

Souhrnem, hodí se pro třídění přirozených nebo celých čísel v malém rozsahu. Nehodí se pro třídění celých čísel bez znalosti rozsahu, reálných čísel a strukturovaných dat, např. stringů.

Algoritmus

Algoritmus nejprve zleva (či zprava) projde vstupní pole a pro každý prvek, na který narazí, zvýší v pomocném poli četnost výskytu tohoto prvku o 1. Poté, co má v pomocném poli zaznamenán počet výskytů, poupraví toto pole následujícím způsobem: ke každé položce přičte počet výskytů všech předchozích položek. Tím u každé položky v pomocném poli získá přesnou pozici hranice, na které bude v seřazeném poli. Následuje vlastní řazení. Algoritmus začne zprava procházet neseřazené pole a pro každý prvek, na který narazí, se podívá do pomocného pole na horní hranici pro umístění. Na tuto hranici ho umístí a zároveň ji sníží o jedna. Takto postupuje, dokud neprojde celé pole. Tím je řazení skončeno.

Pokud má být algoritmus stabilní, potřebuje (jinou) vhodnou implementaci, která neplyne z obecného popisu výše. Konkrétněji, potřebuje si už v pomocném poli připravit indexy tak, aby každou (nesouvislou) skupinu stejných hodnot ve vstupním poli ukládal do výstupního pole ve stejném pořadí, tj. stabilně. Pokud se vstup prochází zepředu, musíme skupinu ukládat na stoupající indexy ve výstupním poli, tj. od dolní hranice.

Pseudokód např. v lit.

Doplnění, vysvětlení, ...

Rozsah dat K může být větší než velikost vstupu N. Pomocné pole má velikost K, K=>M, protože některé hodnoty z rozsahu se nemusí na vstupu vyskytovat. Pomocné pole procházíme a započítáme do složitosti jako O(K) např. při jeho inicializaci.

Alg. má pro efektivní implementaci omezující podmínky (viz předpoklady) a nelze ho použít pro všechna data. Ale protože není založen na porovnávání, tak může mít lineární složitost (O(N+K) místo O(N \log N) pro porovnávací algoritmy). Při nesplnění předpokladů rychlost degraduje a přestane být důvod ho používat.

Pragmaticky, máme přehršel třídících a řadících algoritmů (nehodící si škrtněte), tak si vybereme ten vhodný, který máme v knihovně. Na opravdu velká data jsou specializované externí třídící algoritmy, dodnes (2018) fungující pro magnetické pásky. Na disky ještě nedošlo a např. Funnelsort taky ne.

Ale i Counting sort lze použít pro předtřídění (předřazeni?) dat v dávkách, které se vejdou do operační paměti (nebo do keše). Následně se už uspořádané dávky (en: chunk) třídí na disku, např. algoritmem založeným na vícecestném mergesortu.

Asymptotická náročnost

Časová náročnost

Časová náročnost je lineární k počtu prvků a počtu různých prvků (O(N+K)), protože musíme pro každý prvek zvýšit údaj o četnosti v pomocném poli, a pak každý prvek znovu vypsat do výsledného setříděného pole.

Paměťová náročnost

Paměťová náročnost je (O(M)), protože si potřebujeme pamatovat četnosti pro všechny hodnoty prvků. Celé pole, které se řadí, není potřeba mít v paměti, proto se tento algoritmus dá použít i na pole, která jsou tak velká, že se nemohou do paměti celá vejít.

Algoritmus nepracuje na místě, protože potřebuje pomocné pole a (při běžné implementaci) přesouvá prvky ze vstupního pole do výstupního pole. Vstupní pole procházíme sekvenčně (zepředu nebo zezadu) dvakrát, tak tyto data mohou být ve streamu, ale výstupní (i pomocné) pole měníme přímým přístupem podle indexu (tj. náhodně), tak se je hodí mít v paměti. Jistě, gůůglí Bigtable by si s tím poradila. Ale asi ne rychle.

Příklad

V příkladu ukážeme, jak setřídit pole čísel 1, 4, 2, 4, 1, 3, 1.

Pomocné pole (číslo - počet výskytů):

1 - 3x
2 - 1x
3 - 1x
4 - 2x

Přepočet na hranice prvku (číslo - index konce pole)

1 - 3
2 - 4
3 - 5
4 - 7

V prvním kroku máme umístit číslo 1. Protože víme, že číslo jedna má 3 výskyty, umístíme jej na 3. pozici a snížíme v pomocném poli počet zbývajících výskytů na 2.
[ ][ ][1][ ][ ][ ][ ]

Pomocné pole po prvním kroku

1 - 2
2 - 4
3 - 5
4 - 7

Další kroky probíhají analogicky, zde je uvedeno, jak se bude postupně plnit seřazené pole:

[ ][ ][1][ ][3][ ][ ]
[ ][1][1][ ][3][ ][ ]
[ ][1][1][ ][3][ ][4]
[ ][1][1][2][3][ ][4]
[ ][1][1][2][3][4][4]
[1][1][1][2][3][4][4] - seřazené pole a algoritmus končí

Externí odkazy

• Vizualizace řazení v HTML5
• Vizualizace řazení pomocí Java appletu
• Popis implementace v jazyku java
• Martin Mareš, Tomáš Valla, Průvodce labyrintem algoritmů, [1] pdf